package com.acyouzi.leetcode.dp;

import java.util.HashMap;

/**
 * 17/9/24 10:23
 *
 * @author sunxu
 */
public class CanIWin {
  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    // 搞一个 map，其中存储的是状态(0101 这样子的数据)
    int sum = (1+maxChoosableInteger)*maxChoosableInteger/2;
    if(sum < desiredTotal) return false;
    HashMap<String,Boolean> map = new HashMap<>();
    char[] flag = new char[maxChoosableInteger+1];
    for (int i = 0; i <= maxChoosableInteger; i++) flag[i] = '0';
    return helper(map,flag,desiredTotal,maxChoosableInteger);
  }
  private boolean helper(HashMap<String,Boolean> map, char[] flag, int sum, int len) {
    if (sum <= 0 ) return false;
    String key = String.valueOf(flag);
    if (!map.containsKey(key)) {
      for (int i = 1; i <= len; i++) {
        if (flag[i] != '1'){
          flag[i] = '1';
          if (!helper(map,flag,sum-i,len)){
            // 下一级是 false, 本次是 true;
            map.put(key, true);
            flag[i] = '0';
            return true;
          }
          flag[i] = '1';
        }
      }
    }
    return map.get(key);
  }
}
